1. Field of the Invention
The present invention relates to a memory device used in vector processor. More particularly it relates to a method of accessing a memory in which data are stored in addresses separated from each other by a constant stride. The invention especially intends to increase the throughput of the memory device.
2. Description of Prior Art
In recent high speed vector processors, the main memory device is divided into a plurality of memory banks enabling parallel access thereto in order to decrease the total access time to many data, and to provide a fail-soft structure for the memory device, that, is to minimize the destruction of the memories when failure occurred.
The data stored in a memory device is accessible by indicating in a program the address numbers of the memory cells where the desired data are stored. In order to make access to a plurality of data which are stored in memory cells having contiguous address numbers, it is unnecessary to indicate all of these addresses in a program. The computer is provided with an address generator which outputs successively the necessary addresses when the starting address and the end address are given, or when the starting address and the length of the address chain are given. So, the data are automatically read out or stored in succession. The group of addresses in which the data are stored in such manner is called in the art a vector address, and a method to make access to such data is called a vector access.
The memory device has a plurality of memory cells arranged in several banks. Each of the memory cells stores a data element, and each of the memory locations are numbered. This number is called an address number or address index. The numbering is interleaved with each bank in a manner as shown in upper half of FIG. 1. Namely, the memory cells are numbered from the first row of the first bank, next to the first row of the second bank and then the first row of the third bank, and so on. And when the first row of the final bank is numbered, the second row of each is numbered in succession. FIG. 1 shows only four banks, and the numbering, therefore, is four-way interleaved, but in general the memory device is provided with many banks depending on the size of memory. So, if the memory device is provided with n banks, the addresses are n-way interleaved, and the number n to identify each of the banks is called the bank number or bank index.
An example of vector access is shown in FIG. 2. When the first address (4 in this example) and the end address (27) are given, the address generator outputs the all of the address indices indicated by the hatching in succession of the address number. The data stored in these memory cells are accessed. The hatched area is a vector address. Such an address is called a contiguous vector address or sequential address and the method to accessing the addresses is called contiguous vector access or sequential access.
But in data processing, it often occurs that it is necessary to make access to the data which are stored in the memory cells which have indices skipping a constant number. An example is shown in FIG. 3. In this example, the number of the banks is 16 so, the address numbers are 16-way interleaved. In FIG. 3, the requested addresses are 0, 3, 6, 9, C, F ... These numbers are expressed in hexa-decimal numerals. They are stored in the addresses skipping two addresses between each other. The difference of the address numbers between neighboring addresses is called as a distance, or a stride. In the above example, therefore, the distance is three. Such addressing is called in the art a distanced vector address or a constant stride address, and the method of accessing such addresses is called a distanced vector access or a constant stride access.
While a method of accessing each memory indicating all of their addresses one by one in a program is called sometimes a scalar access.
The requirement of distanced vector access often occurs in vector or matrix processing. Of course there are many cases other than the matrix processing which need the distanced vector access. A process of distanced vector access will be explained briefly taking an example of matrix processing. Consider a matrix of m row and n column like as, ##EQU1## the data elements a.sub.mn are usually arranged in sequence of column index n or row index m, and they are stored in respective address of the memory device in order of the element index mn. If it is requested to access the data elements in order of the column index n, that is in succession of a.sub.11, a.sub.12, a.sub.13. . . , the contiguous vector access described above is convenient. But if it is requested to access the data elements in the order of row index m, that is in the succession of a.sub.11, a.sub.21, a.sub.31 . . . , there occurs the necessity of the distanced vector access.
The memory device is provided with a bank controller which controls the access to each of the banks or gives priority to the access. While a bank is being accessed by a processor, the bank controller prohibits further access to this bank. When access to this bank is over, the bank controller enables other processors to access this bank. At first, such bank controllers were provided for each of the banks. But, as the number of the banks increases, the expense for the hardware increases, therefore in modern processors, there are proposed various bank controlling method to reduce the number of bank controllers and to economize the memory device.
In an exemplary bank control method, a time slot is given to each of the banks during which the access to the bank is allowed, and the time slot is shifted from one bank to another in sequence. For example, as shown in lower half of FIG. 1, the access to bank 1 is allowed only in the time period T.sub.1. During this time period, the access to other banks is forbidden. In the next time period T.sub.2, the bank 2 is enabled, and the other banks are forbidden. In the following time period T.sub.3, only the bank 3 is enabled. Like such manner, all of the banks are enabled subsequently one by one. Such control is called as sequential bank control.
Another proposed controlling method is grouping of the banks, and a access controller is provided for each of the groups. For example, all of the 12 banks are grouped into four groups each having three banks. Each bank controller checks three banks, and if one of the banks in the group is responding to an access, it forbids access to the group. In the description hereinafter, the disclosure will be given with respect to the sequential bank control, but it will be apparent for the one skilled in the art that the discussion can be applied to any of such bank controlling method.
As an example, how data is stored in a distanced vector addresses and accessed in an existing processor will be described. FIG. 3 is an address chart having sixteen-way interleave and a stride or distance of three. As has been mentioned before, these banks are enabled one by one to respond to an access within a predetermined time slot. So, in this case, first, the data in address 0 in bank 0 is accessed during the first time slot. In the description hereinafter, a memory cell having an address number and a data stored in it are both called simply an address unless specially identified. So, a wording "access to an address" means to access to a data stored in a memory cell having the address number. The next address to be accessed is 3 in the bank 3, but the processor is forbidden to access to the bank 3 during next two time slots. Then in the fourth time slot, the address 3 in the bank 3 is accessed. In such a manner, if one address is accessed, the following two time slots are skipped without accessing any bank. In the above example, therefore, only one address is accessed in each three time slots in the data sequence 0, 3, 6, 9, C, and F. Then the addresses 12, 15, 18, 1B . . . are accessed in, succession. Such a process is repeated until all of the distanced vector addresses are accessed. As can be understood form above explanation, the access to each of the data elements in a vector address is done during only one time slot among several time slots covering one distance of the address. So, the total access time to the distanced vector address takes a long time. In the example of FIG. 3, 48 time slots are necessary to access to 16 addresses. Generally, the throughput of the memory device decreases approximately 1/D when it is accessing a distanced vector address having a distance D, compared to that when it is accessing to a contiguous vector address having the same number of the data elements.
The reason why such an inconvenience occurs is attributed to the address generator. In a conventional address generator, the addresses are generated in order of the address indices. Namely, in the case of FIG. 3, the addresses are generated in order of 0, 3, 6 ... 2A and 2D. Therefore, the processor has to the wait several time slots before it accesses to the next address. An exemplary circuit configuration of an existing address generator is shown in FIG. 4. In this figure, a start address is set in a start address register (SADR) 51 and distance is set in a distant register (DIST) 52. In FIG. 4, the value of distance 3 is added to the start address 0 by an adder 53, producing a new address number 3. This number is registered in an address register 54 via the register 51. And then, the distance 3 is again added to the address number 3, producing a new address number 6, and so on. In such a manner, new addresses are generated one after another in order of the address index. Accordingly, the addresses 0, 3, 6, 9, C, F, 12, 15, . . ., are obtained in sequence. These generated addresses are stored in the address register 54 for a while, and accessing of the memory 55 is carried out.
It will be understood that accessing the memory with a constant stride using the conventional address generator takes very long time. This is a big determined to the processing speed in a high speed vector processor.